package mosdi.matching;

import java.util.Arrays;

public class HorspoolMatcher {

	public static int comparisons = -1;

	public static int[] computeShiftTable(int alphabetSize, int[] pattern) {
		int[] shift = new int[alphabetSize];
		Arrays.fill(shift, pattern.length);
		for (int i=0; i<pattern.length-1; ++i) {
			shift[pattern[i]]=pattern.length-1-i;
		}
		return shift;
	}
	
	public static int findMatches(int alphabetSize, int[] text, int[] pattern) {
		int[] shift = computeShiftTable(alphabetSize, pattern);
		int comparisons = 0;
		int count = 0;
		int n = pattern.length-1;
		while (n<text.length) {
			int i = 0;
			while (i<pattern.length) {
				comparisons+=1;
				if (text[n-i]!=pattern[pattern.length-i-1]) break;
				i+=1;
			}
			if (i==pattern.length) {
				count+=1;
			}
			n+=shift[text[n]];
		}
		// Log.println(Log.Level.DEBUG, "Horspool: Comparisons: "+comparisons);
		HorspoolMatcher.comparisons = comparisons;
		return count;
	}
	
}
